|
The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two hyperedges adjacent when they have a nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph. Questions about line graphs of hypergraphs are often generalizations of questions about line graphs of graphs. For instance, a hypergraph whose edges all have size ''k'' is called ''k ''-uniform. (A 2-uniform hypergraph is a graph.). In hypergraph theory, it is often natural to require that hypergraphs be ''k''-uniform. Every graph is the line graph of some hypergraph, but, given a fixed edge size ''k'', not every graph is a line graph of some ''k''-uniform hypergraph. A main problem is to characterize those that are, for each ''k'' ≥ 3. A hypergraph is linear if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph . ==Line graphs of ''k''-uniform hypergraphs, ''k'' ≥ 3== characterized line graphs of graphs by a list of 9 forbidden induced subgraphs. (See the article on line graphs.) No characterization by forbidden induced subgraphs is known of line graphs of k-uniform hypergraphs for any ''k'' ≥ 3, and showed there is no such characterization by a finite list if ''k'' = 3. characterized line graphs of graphs in terms of clique covers. (See Line Graphs.) A global characterization of Krausz type for the line graphs of ''k''-uniform hypergraphs for any ''k'' ≥ 3 was given by . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Line graph of a hypergraph」の詳細全文を読む スポンサード リンク
|